/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hoja10;
import java.io.*;
/**
 *
 * @author RAUL
 */
public class Floyd {
  
    
    /** Crea un nuevo floyd*/
    public Floyd() {
    }
    
    
    
        
   /*Matriz de Distancias 100x100 ---- Distance Matrix 100x100 nodes 99999 = infinite */             
    int A[][]={
        
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 100, 220, 86, 45, 34, 23, 80, 76, 556, 344, 123, 356, 678, 54, 598, 678, 765, 453, 21, 44, 65},
        {0,20, 0, 45, 56, 57, 78, 220, 100, 389, 435, 654, 32, 65, 677, 89, 677, 890, 932, 123, 543, 65, 54},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
        {0,},
    };
                
   /*Creating Adjacency Matrix*/
   int S[][] = new int [101][101];
        
        for (int w=1; w<= 22; w++)
            for (int v=1; v<= 22; v++)
                if (w!=v)
                    S[w][v] = v;
                else
                    S[w][v] = 0;

        
        
        /*Beginning of Floyd's Matrix Iterations*/
        for (int m=1; m<=22; m++)
            for (int n=1; n<=22; n++)
                for (int p=1; p<=22; p++)
                    if (n != m && p!=m){
                        if (A[n][m] + A[m][p] < A[n][p]){/*Checks if there is a shortest path, and assign the new value*/
                            A[n][p] = A[n][m] + A[m][p];
                            S[n][p] = m;
                            
                        }else
                            A[n][p] = A[n][p];
                            
            
            
                    }
               
               String Cds [] = { /*Array used to read the city name*/
 "Cabo San Lucas" ,
 "La Paz" ,
 "Ciudad Constitucion" ,
 "Loreto" ,
 "Mulege" ,
 "Santa Rosalia" ,
 "San Ignacio" ,
 "Guerrero Negro" ,
 "Rosario" ,
 "Ensenada" ,
 "Tijuana" ,
 "Mexicali" ,
 "Rio Colorado" ,
 "Sonoyta" ,
 "Caborca" ,
 "Santa Ana" ,
 "Agua Prieta" ,
 "Hermosillo" ,
 "Yecora" ,
 "Guaymas" ,
 "Ciudad Obregon" ,
 "Navojoa" ,
 "Los Mochis" ,
 "Guasave" ,
 "Guamuchil" ,
 "Culiacan" ,
 "Mazatlan" ,
 "Tepic" ,
 "Guadalajara" ,
 "Puerto Vallarta" ,
 "Barra de Navidad" ,
 "Lagos de Moreno" ,
 "Matamoros" ,
 "Ciudad Victoria" ,
 "Tampico" ,
 "Nuevo Laredo" ,
 "Reynosa" ,
 "Ciudad Cuahutemoc" ,
 "Chihuahua" ,
 "Villa Ahumada" ,
 "Ciudad Juarez" ,
 "Camargo" ,
 "Torreon" ,
 "Saltillo" ,
 "Monclova" ,
 "Piedras Negras" ,
 "Monterrey" ,
 "Durango" ,
 "Zacatecas" ,
 "San Luis Potosi" ,
 "Ciudad Valles" ,
 "Aguascalientes" ,
 "Colima" ,
 "Lazaro Cardenas" ,
 "Morelia" ,
 "Chilpancingo" ,
 "Zihuatanejo" ,
 "Acapulco" ,
 "Puerto Escondido" ,
 "Bahias de Huatulco" ,
 "Oaxaca" ,
 "Huajuapan" ,
 "Tuxtepec" ,
 "Matias Romero" ,
 "Tapanatepec" ,
 "Salina Cruz" ,
 "Poza Rica" ,
 "Veracruz" ,
 "Xalapa" ,
 "La Tinaja" ,
 "Cordoba" ,
 "Acayucan" ,
 "Coatzacoalcos" ,
 "Guanajuato" ,
 "Leon" ,
 "Irapuato" ,
 "Queretaro" ,
 "Pachuca" ,
 "Huejutla" ,
 "Tulanzingo" ,
 "Tlaxcala" ,
 "Mexico DF" ,
 "Toluca" ,
 "Atlacomulco" ,
 "Cuernavaca" ,
 "Puebla" ,
 "Izucar de Matamoros" ,
 "Tehuacan" ,
 "Tuxtla Gutierrez" ,
 "San Cristobal de las Casas" ,
 "Tapachula" ,
 "Ococingo" ,
 "Villahermosa" ,
 "Frontera" ,
 "Ciudad del Carmen" ,
 "Escarsega" ,
 "Campeche" ,
 "Merida" ,
 "Cancun" ,
 "Chetumal" 
 
};


        
        
       

}
